# -*- coding: utf-8 -*-

# __date:       2021/7/12
# __author:     Yang Chao
# __function:


class Solution:

    table = {'2': ['a', 'b', 'c'],
             '3': ['d', 'e', 'f'],
             '4': ['g', 'h', 'i'],
             '5': ['j', 'k', 'l'],
             '6': ['m', 'n', 'o'],
             '7': ['p', 'q', 'r', 's'],
             '8': ['t', 'u', 'v'],
             '9': ['w', 'x', 'y', 'z']}

    def letterCombinations(self, digits: str) -> List[str]:
        """
        方案一：递归求解
            结束条件为len(digits) == 0
            每次将当前的遍历到字符加入
        :param digits:
        :return:
        """
        if len(digits) == 0:
            return []
        self.res = []
        self.find_res("", digits)
        return self.res

    def find_res(self, s, digits):
        if len(digits) == 0:
            self.res.append(s)
        else:
            cur_str = self.table[digits[0]]
            for c in cur_str:
                self.find_res(s + c, digits[1:])